package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.swap

/**
 * Shell sort is an in-place comparison sort that can be seen as either a generalization of insertion sort or a
 * variation of bubble sort. It starts by sorting pairs of elements far apart from each other and progressively
 * reducing the gap between elements to be compared. The final iteration uses a gap of 1, which is equivalent to
 * an insertion sort. The algorithm's time complexity depends on the chosen gap sequence.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n log n)
 * Average performance:          Depends on the gap sequence
 * Worst-case space complexity:  O(1)
 * Stable: No
 */

const val GAP = 3

/**
 * Shell sort is an in-place comparison sort that can be seen as either a generalization of insertion sort or a
 * variation of bubble sort. It starts by sorting pairs of elements far apart from each other and progressively
 * reducing the gap between elements to be compared. The final iteration uses a gap of 1, which is equivalent to
 * an insertion sort. The algorithm's time complexity depends on the chosen gap sequence.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n log n)
 * Average performance:          Depends on the gap sequence
 * Worst-case space complexity:  O(1)
 * Stable: No
 */
fun<T : Comparable<T>> Array<T>.shellSort(){
    val size = this.size
    var gap = 1
    while (gap < size / GAP) {
        gap = gap * GAP + 1
    }

    while (gap >= 1) {
        for (i in gap until size) {
            var j = i
            while (j >= gap && this[j - gap] > this[j]) {
                swap(j, j - gap)
                j -= gap
            }
        }
        // Reduce the gap for the next iteration
        gap /= GAP
    }
}